#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
void mergesort(int* tem, int* p, int begin, int end)
{
	if (begin >= end)
		return;
	int left = begin;
	int right = end;
	int mid = (end - begin) / 2 + begin;
	mergesort(tem, p, begin, mid);
	mergesort(tem, p, mid + 1, end);
	int begin2 = mid + 1;
	int end2 = end;
	end = mid;
	int j = 0;
	while (begin <= end && begin2 <= end2)
	{
		if (p[begin] >= p[begin2])
			tem[j++] = p[begin2++];
		if (p[begin] <= p[begin2])
			tem[j++] = p[begin++];
	}
	if (begin <= end)
	{
		while (begin <= end)
			tem[j++] = p[begin++];
	}
	else
	{
		while (begin2 <= end2)
			tem[j++] = p[begin2++];
	}
	memmove(p + left, tem, j * sizeof(int));
}
void test1()
{
	int arr[8] = { 10,6,7,1,3,9,4,2 };
	int sz = sizeof(arr) / sizeof(int);
	int* tem = (int*)malloc(sizeof(int) * sz);
	assert(tem);
	mergesort(tem, arr, 0, sz - 1);
	int i = 0;
	for (i = 0; i < sz; i++)
		printf("%d->", arr[i]);
}
int main()
{
	test1();
	return 0;
}